package com.cyy.tree;

import com.cyy.printer.BinaryTreeInfo;
import com.cyy.set.Set.Visitor;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树接口
 * @author 会玩的洋洋
 * @since 2022-02-22
 * @param <E>
 */
public class BinaryTree<E> implements BinaryTreeInfo {
    /**
     * 二叉树根节点
     */
    protected Node<E> root;
    /**
     * 记录二叉树节点数量
     */
    protected int size;

    /**
     * 二叉树中的节点数量
     * @return int
     */
    public int size() {
        return size;
    }

    /**
     * 判断树是否为空
     * @return boolean
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     *  清空二叉树
     */
    public void clear() {
        size = 0;
        root = null;
    }

    /**
     * 判断是否为完全二叉树
     * @return boolean
     */
    public boolean isComplete() {
        if (root == null) {
            return false;
        }
        // 层序遍历 （广度优先搜索）
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            /*
                1. 度为1的子树 只有左叶子节点
                2. 当节点的度为0时，后边的节点均为叶子节点
                3. 当没有右子节点时，后边的节点均为叶子节点
             */
            if (leaf && !node.isLeaf()) {
                return false;
            }

            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                return false;
            }
            if (node.right != null) {
                queue.offer(node.right);
            } else {
                leaf = true;
            }
        }
        return true;
    }

    /**
     * 计算二叉树高度
     * @return int
     */
    public int height() {
        int height = 0;
        if (root == null) {
            return height;
        }
        // 记录一层的节点数量
        int levelSize = 1;
        // 层序遍历 （广度优先搜索）
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            --levelSize;

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }

            // 代表新的一层
            if (levelSize == 0) {
                height++;
                levelSize = queue.size();
            }
        }
        return height;
    }

    /**
     * 获取某一节点的高度
     * @param node 所求高度的节点
     */
    public int height(Node<E> node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }

    /**
     * 前序遍历 递归版本
     */
    public void preorderTraversal(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        preorderTraversal(root, visitor);
    }

    private void preorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
        preorderTraversal(node.left, visitor);
        preorderTraversal(node.right, visitor);
    }

    /**
     * 前序遍历 非递归版本
     */
    public void preorderTraversal2(Visitor<E> visitor) {
        if (root == null || visitor == null) {
            return;
        }
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node<E> node = stack.pop();
            if (visitor.stop) {
                return;
            }
            visitor.stop = visitor.visit(node.element);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    /**
     * 中序遍历 递归
     */
    public void inorderTraversal(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        inorderTraversal(root, visitor);
    }

    private void inorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) {
            return;
        }
        inorderTraversal(node.left, visitor);
        visitor.stop = visitor.visit(node.element);
        inorderTraversal(node.right, visitor);
    }

    /**
     * 中序遍历  非递归
     */
    public void inorderTraversal2(Visitor<E> visitor) {
        if (root == null || visitor == null) {
            return;
        }
        Node<E> node = root;
        Stack<Node<E>> stack = new Stack<>();
        while (true) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else if (stack.isEmpty()) {
                return;
            } else {
                // 弹出栈顶元素
                node = stack.pop();

                if (visitor.visit(node.element)) {
                    return;
                }
                // 继续从右子节点进行循环
                node = node.right;
            }
        }
    }

    /**
     * 后序遍历 递归
     */
    public void postorderTraversal(Visitor<E> visitor) {
        if (visitor == null) {
            return;
        }
        postorderTraversal(root, visitor);
    }

    private void postorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) {
            return;
        }
        postorderTraversal(node.left, visitor);
        postorderTraversal(node.right, visitor);
        if (visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
    }

    /**
     * 后序遍历 非递归
     */
    public void postorderTraversal2(Visitor<E> visitor) {
        if (root == null || visitor == null) {
            return;
        }
        Node<E> prev = null;
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node<E> node = stack.peek();

            if (node.isLeaf() || (prev != null && prev.parent == node)) {
                prev = stack.pop();
                if (visitor.visit(node.element)) {
                    return;
                }
            } else {
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }
    }

    /**
     * 层序遍历
     */
    public void levelOrderTraversal(Visitor<E> visitor) {
        if (root == null || visitor == null) {
            return;
        }

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.visit(node.element)) {
                return;
            }

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**
     * 获取前驱结点
     * @param node 目标节点
     * @return Node<E> 前驱结点
     */
    public Node<E> predecessor(Node<E> node) {
        if (node == null) {
            return null;
        }

        // 1. 判断 left 节点不为 null 的情况，遍历 right 即可
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }

        // 2. 如果 left 为 null 的情况， 一种是 parent 为 null  并且 父节点的左子节点不是自身
        while (node.parent != null && node.parent.left == node) {
            node = node.parent;
        }
        return node.parent;
    }

    /**
     * 获取后驱节点
     * @param node 目标节点
     * @return Node<E>
     */
    public Node<E> successor(Node<E> node) {
        if (node == null) {
            return null;
        }

        // 1. 判断 right 不为 null 的情况， 遍历 left 即可
        Node<E> s = node.right;
        if (s != null) {
            while (s.left != null) {
                s = s.left;
            }
            return s;
        }

        // 2. 判断 left 为 null 的情况，向上查找 parent 不为 null 并且 parent 的右子树不为 自身
        while (node.parent != null && node.parent.right == node) {
            node = node.parent;
        }
        return node.parent;
    }

    @Override
    public Object root() {
        return this.root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        return node;
    }


    protected static class Node<E> {
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        E element;

        public Node() {
        }

        public Node(Node<E> parent, E element) {
            this.parent = parent;
            this.element = element;
        }

        public Node(Node<E> left, Node<E> right, Node<E> parent, E element) {
            this.left = left;
            this.right = right;
            this.parent = parent;
            this.element = element;
        }

        /**
         * 判断是否为叶子节点
         * @return boolean
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 是否是度为 2 的节点
         * @return boolean
         */
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        /**
         * 判断是否为左子节点
         * @return boolean
         */
        public boolean isLeftChildren() {
            return parent != null && this == parent.left;
        }

        /**
         * 判断是否为右子节点
         * @return boolean
         */
        public boolean isRightChildren() {
            return parent != null && this == parent.right;
        }

        /**
         * 获取兄弟节点
         * @return Node<E>
         */
        public Node<E> sibling() {
            if (isLeftChildren()) {
                return parent.right;
            } else if (isRightChildren()) {
                return parent.left;
            }
            return null;
        }

        @Override
        public String toString() {
            String parentString = "null";
            if (parent != null) {
                parentString = parent.element.toString();
            }
            return element + "_p(" + parentString + ")";

        }
    }

}
